home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / cubezip.exe / TECHTALK.TXT < prev   
Text File  |  1991-10-15  |  11KB  |  174 lines
  1.  
  2.         ┌──────────────────────────────────────────────────────────────┐
  3.         │                                                              │
  4.         │                   Steve Gibson's InfoWorld                   │
  5.         │                   Magazine TechTalk Column                   │
  6.         │                    for InfoWorld Issue #41                   │
  7.         │                                                              │
  8.         └──────────────────────────────────────────────────────────────┘
  9.  
  10.                   ╔═══════════════════════════════════════════╗
  11.                   ║  Beyond Accounting: How a computer might  ║
  12.                   ║  go about solving a wooden block puzzle.  ║
  13.                   ╚═══════════════════════════════════════════╝
  14.  
  15.         This week marks the end of my fifth consecutive year writing 
  16.         this TechTalk column for you every week. Somehow, despite the 
  17.         generation of 255 separate columns, I've never missed a week nor 
  18.         run out of ideas and discoveries to share. I remember worrying, 
  19.         many years ago, that I might soon exhaust the supply of 
  20.         worthwhile topics. But as this TechTalk column begins its sixth 
  21.         year, I see no such end in sight. I suppose that it won't come 
  22.         as news to any of you that I'm a total technology junkie who 
  23.         just can't get enough. Although many people regard the culture, 
  24.         lore, and details surrounding computers as boring, 
  25.         incomprehensible, and "nerdy", you're reading this right now 
  26.         because you haven't shut yourself down with such thoughts. So 
  27.         let's glide forward together into the sixth year of the TechTalk 
  28.         column, seeing what new amazing applied miracles our 
  29.         technologies will enable for us tomorrow. 
  30.  
  31.         I recently ran across a gifted machinist who has a penchant for 
  32.         puzzles. The first thing Bob handed me was an assembly of wooden 
  33.         pieces which were keeping a 5 cent nickel captive. A hidden 
  34.         "gravity lock" required a subtle twist of the wrist at just the 
  35.         right moment in order to free the nickel. Well, luck must have 
  36.         been smiling upon me when I stumbled upon the solution for this 
  37.         first puzzle almost immediately. Bob quickly determined that 
  38.         he'd found a fellow puzzler, and so pulled a slightly bowed 
  39.         stick of wood from another pocket. My eyebrows peaked when I saw 
  40.         that this solid and almost featureless stick would only spin in 
  41.         one direction. When given a hard spin in the "wrong" direction, 
  42.         the stick would slow down and stop, then resume spinning in the 
  43.         "correct" direction. Looking carefully at the stick I saw that 
  44.         the specific shape of Bob's stick transferred the energy from 
  45.         spinning in the "wrong" direction spin into a vibration along 
  46.         the stick's long axis, this allowing the stick to store the 
  47.         energy of the spin in another form (vibration), and then to turn 
  48.         this vibrational energy back into a resumed spin in the 
  49.         "correct" direction. 
  50.  
  51.         Over the course of the next several months I was able to solve 
  52.         the various puzzles Bob presented. Then Wednesday before last he 
  53.         handed me nine blocky pieces of wood with the instructions to 
  54.         assemble them into a 3 by 3 by 3 checkerboard cube. He had a 
  55.         sample cube rubberbanded together as a demonstration of the 
  56.         objective. After struggling without result for a few minutes (to 
  57.         Bob's extreme delight), it became clear that no solution lay 
  58.         near. So I took the nine loose pieces home with me. Just as I 
  59.         was leaving Bob made my day by mentioning that it had taken him 
  60.         over a month to assemble the cube. Great.
  61.  
  62.         Later that evening, as I was messing around with the nine 
  63.         separate pieces that refused to assemble themselves into 
  64.         anything even remotely resembling a cube, let alone a 
  65.         checkerboard, I began imagining a month of my life slipping 
  66.         away. Not long afterward I decided to write a computer program 
  67.         to solve Bob's wooden block puzzle. 
  68.  
  69.         It's obvious that computers can do things such as manage 
  70.         accounting data, compute interest rates, and recalculate 
  71.         spreadsheets, but it's not nearly as obvious how a computer, 
  72.         which fundamentally adds and subtracts numbers, might be used to 
  73.         solve a puzzle as abstract as this one. The key to applying a 
  74.         computer to a problem that lies outside the domain of numerics 
  75.         is to represent the problem within the domain of numbers. In 
  76.         other words, we must first invent a representation system that 
  77.         can be used to contain and describe the problem numerically. 
  78.         Once we have established a means of representing the reality of 
  79.         the problem numerically, a computer can be programmed to 
  80.         meaningfully manipulate the result. 
  81.  
  82.         The puzzle pieces consisted of simple light and dark blocks of 
  83.         wood glued together into complex shapes. Since some of the 
  84.         wooden blocks consisted of half cubes, I needed a way of 
  85.         describing where there was wood and where there wasn't within 
  86.         each cube-space. Conveniently, a complete cube has eight 
  87.         corners, just as a computer's data byte has eight bits, so the 
  88.         multiple-block configuration of the various pieces could be 
  89.         described by a collection of data bytes where the individual 
  90.         bits in each byte represented which corners of their 
  91.         corresponding cubes contained wood. Are you with me so far? 
  92.  
  93.         Since the final assembled 3 by 3 by 3 checkerboard "master cube" 
  94.         would be built up from an array of 27 smaller cubes (3x3x3=27), 
  95.         I decided to use a 27 byte data array to describe the current 
  96.         composition of the master cube as the computer worked toward its 
  97.         solution. The first nine data bytes would represent the 3 by 3 
  98.         pattern of wood in the top layer of the assembled master cube, 
  99.         the next nine bytes would represent the wood in the middle 
  100.         layer, and the last nine would represent the wood in the bottom 
  101.         layer. This 27-byte data array would thus serve as a master 
  102.         template for modelling the 3 dimensional space occupied by the 
  103.         master cube. Sliding wooden pieces around within this 3 
  104.         dimensional space would simply consist of copying data bytes 
  105.         from one location to another. 
  106.  
  107.         Computers excel at performing repetitive tasks, and they can be 
  108.         quite fast at doing so if they're programmed correctly. So my 
  109.         brute force "strategy" for solving this puzzle would be to 
  110.         explore all possible arrangements of all of the pieces. 
  111.         Somewhere among all of the possible combinations of the 
  112.         individual pieces there would be one combination where none of 
  113.         the pieces collide within the 3 by 3 by 3 master cube space. 
  114.         This combination would be the solution to the puzzle.
  115.                  
  116.         Since this meant that each of the nine wooden pieces needed to 
  117.         be placed into every possible location and orientation within 
  118.         the 3 by 3 by 3 master cube, I decided I decided to begin by 
  119.         having the computer generate every possible position for each 
  120.         piece within the space of the master cube. For each of the nine 
  121.         puzzle pieces the computer would create a set of 27-byte arrays 
  122.         with each 27-byte array representing one piece floating within 
  123.         the 3 dimensional space of the 3 by 3 by 3 master cube. Each of 
  124.         the possibilities was created by describing the way the wood 
  125.         would move within the master cube when it was rotated about, and 
  126.         translated along, each of its three axis. By exploring all 
  127.         possible "translations" for every possible "rotation", and 
  128.         eliminating duplications, tables representing all possible piece 
  129.         locations were created. Written in pure assembly language (as is 
  130.         still my preference) the computer required less than a second to 
  131.         build the images of each piece occupying every possible 
  132.         position. 
  133.                  
  134.         It turned out that eight of the nine pieces could occupy 72 
  135.         different locations within a 3 by 3 by 3 cube, and that the 
  136.         remaining piece could occupy any of 96 locations. This meant 
  137.         that the total number of possible piece configurations for the 
  138.         puzzle would be 72 x 72 x 72 x 72 x 72 x 72 x 72 x 72 x 96 since 
  139.         each piece could be in any of its possible locations when all of 
  140.         the remaining pieces were in any of their possible locations ... 
  141.         all at once! When I multiplied this out I was a bit daunted to 
  142.         see that there were a little more than 69,331 million million 
  143.         possible combinations of pieces! Although the universe would 
  144.         still be intact when the computer had finished exploring them 
  145.         all, Bob and I would be ancient history. 
  146.  
  147.         Salvation lay in the fact that the computer did not need to 
  148.         consider nearly this many total combinations. If the positions 
  149.         of the first two pieces collided within the master cube, there's 
  150.         no reason to worry about any of the 13 million million 
  151.         arrangements of the remaining 7 pieces and if the first three 
  152.         pieces were in collision then the 185,752 million combinations 
  153.         of the remaining 6 piece's could be safely ignored. This process 
  154.         of successive refinement serves to radically lower the total 
  155.         number of possibilities which must be examined. In computer 
  156.         parlance, an exhaustive search through a domain of such 
  157.         possibilities is called a "tree search" and making the decision 
  158.         to limit the search down a particular "branch" of the tree is 
  159.         known as "pruning the search tree." 
  160.  
  161.         When the program was completed I fired it up and watched the 
  162.         screen flicker with a dazzling display of spinning pieces. (I'd 
  163.         given the program a nifty user interface too.) After about eight 
  164.         minutes and over 252,000 calculated moves the computer came to a 
  165.         grinding halt proudly displaying the correct solution to the 
  166.         puzzle. If you'd like to watch your own computer solve this 
  167.         puzzle it's available for downloading, with my complete source 
  168.         code, from the Gibson Research BBS at (714) 830-3300. It's 
  169.         amazing what computers can do! 
  170.  
  171.                                       -30-
  172.  
  173.         ****************************************************************
  174.